// // https://www.lintcode.com/problem/add-and-search-word-data-structure-design/description

// class TrieNode 
// {
// public:
//     TrieNode** children;
//     bool isWord;
//     bool hasChild;
//     TrieNode()
//     {
//         children = new TrieNode*[26];
//         for (int i = 0; i < 26; ++i)
//         {
//             children[i] = NULL;
//         }
//         isWord = false;
//         hasChild = false;
//     }
// };

// class WordDictionary {
// public:
//     TrieNode *root;
//     /*
//      * @param word: Adds a word into the data structure.
//      * @return: nothing
//      */
//     WordDictionary ()
//     {
//         root = new TrieNode;
//     }
    
//     void addWord(string &word) {
//         insert(word);
//     }

//     void insert(string word)
//     {
//         TrieNode* tmp = root;
//         for (int i = 0; i < word.size(); ++i)
//         {
//             int idx = word[i] - 'a';
//             if (!tmp->children[idx])
//             {
//                 tmp->children[idx] = new TrieNode;
//                 tmp->hasChild = true;
//             }
//             tmp = tmp->children[idx];
//         }
//         tmp->isWord = true;
//     }
    
//     bool searchFromNode(TrieNode* node, string word)
//     {
//         // if (word.size() == 1) //注意退出
//         // {
//         //     // return word == '.' || node->children[word-'a']->isWord; 
//         //     // return word[0] == '.' || node->children[word[0] - 'a']->isWord; 
//         //     // Input
//         //     // search(".") 还不能一个孩子节点都没有
//         //     // return (word[0] == '.' && node->hasChild)
//         //     // || node->children[word[0] - 'a']->isWord; 
//         //     return (word[0] == '.' && node->hasChild)
//         //     || (node->children[word[0] - 'a'] && node->children[word[0] - 'a']->isWord); 
//         // }
//         // TrieNode* tmp = root; 注意！！！！
//         TrieNode* tmp = node; 
//         int i = 0;
//         for (; i < word.size(); ++i)
//         {
//             if (word[i] != '.')
//             {
//                 int idx = word[i] - 'a';
//                 if (!tmp->children[idx])
//                 {
//                     return false;
//                 }
//                 tmp = tmp->children[idx];
//             }
//             else
//             {
//                 if (i == word.size() - 1)
//                     return tmp->hasChild;
//                 for (int j = 0; j < 26; ++j)
//                 {
//                     // if(searchFromNode(tmp->children[j], &word[i + 1]))
//                     if(tmp->children[j] && 
//                         searchFromNode(tmp->children[j], &word[i + 1]))
//                         return true;
//                 }
//                 return false; //重要
//             }
//         }
//         return tmp->isWord;
//     }
//     /*
//      * @param word: A word could contain the dot character '.' to represent any one letter.
//      * @return: if the word is in the data structure.
//      */
//     bool search(string &word) {
//         return searchFromNode(root, word);
//     }
// };



// https://www.lintcode.com/problem/add-and-search-word-data-structure-design/description

class TrieNode 
{
public:
    TrieNode** children;
    bool isWord;
    bool hasChild;
    TrieNode()
    {
        children = new TrieNode*[26];
        for (int i = 0; i < 26; ++i)
        {
            children[i] = NULL;
        }
        isWord = false;
        hasChild = false;
    }
};

class WordDictionary {
public:
    TrieNode *root;
    /*
     * @param word: Adds a word into the data structure.
     * @return: nothing
     */
    WordDictionary ()
    {
        root = new TrieNode;
    }
    
    void addWord(string &word) {
        insert(word);
    }

    void insert(string word)
    {
        TrieNode* tmp = root;
        for (int i = 0; i < word.size(); ++i)
        {
            int idx = word[i] - 'a';
            if (!tmp->children[idx])
            {
                tmp->children[idx] = new TrieNode;
                tmp->hasChild = true;
            }
            tmp = tmp->children[idx];
        }
        tmp->isWord = true;
    }
    
    // 递归里面就不要写for循环了..
    bool searchFromNode(TrieNode* node, string word, int idx) //用idx记当前位置
    {
        if (idx == word.length()) {
            return node->isWord;
        }
        if (word[idx] == '.') {
            for (int i = 0; i < 26; ++i)
            {
                if (node->children[i])
                {
                    if (searchFromNode(node->children[i], word, idx + 1))
                        return true;
                }
            }
            return false;
        } else {
            if (!node->children[word[idx] - 'a'])
                return false;
            return searchFromNode(node->children[word[idx] - 'a'], word, idx + 1);
        }
    }
    /*
     * @param word: A word could contain the dot character '.' to represent any one letter.
     * @return: if the word is in the data structure.
     */
    bool search(string &word) {
        return searchFromNode(root, word, 0);
    }
};